//
// Description: 5774. 使用服务器处理任务
// Created by Loading on 2021/5/30.
//

/* 考察优先级队列的使用 */

#include <bits/stdc++.h>

#define PII pair<int, int>

using namespace std;

//释放已结束工作的工作服务器并加入空闲服务器优先级队列
/* 可以将此方法写成lambda表达式形式 */
void
release(priority_queue<PII, vector<PII >, greater<>> &available, priority_queue<PII, vector<PII >, greater<>> &work,
        vector<int> &servers,
        int ts) {
    while (!work.empty() && work.top().first <= ts) {
        available.emplace(servers[work.top().second], work.top().second);
        work.pop();
    }
}

vector<int> assignTasks(vector<int> &servers, vector<int> &tasks) {
    vector<int> res;
    //工作服务器优先级队列，pair为 结束工作时间 与 下标 组合
    priority_queue<PII, vector<PII >, greater<>> work;
    //空闲服务器优先级队列，pair为 服务器权重 与 下标 组合
    priority_queue<PII, vector<PII >, greater<>> available;
    //当前时间戳
    int ts = 0;

    //将所有服务器首先加入空闲服务器优先级队列
    for (int i = 0; i < servers.size(); ++i) {
        available.emplace(servers[i], i);
    }

    /* lambda表达式形式构建方法 */
    auto release = [&](){
        while (!work.empty() && work.top().first <= ts) {
            available.emplace(servers[work.top().second], work.top().second);
            work.pop();
        }
    };

    /* ts不可一直++，当一次性释放多台服务器并有多个任务等待执行的时候，这时会有多个任务一起开始执行，一直++ts会导致任务执行时间错误 */
    for (int i = 0; i < tasks.size();) {
        ts = max(ts, i);
//        release(available, work, servers, ts);
        release();
        if (!available.empty()) {//有空闲服务器
            res.emplace_back(available.top().second);
            work.emplace(ts + tasks[i], available.top().second);
            available.pop();
            ++i;
        } else {//没有空闲服务器，ts置为最先释放的服务器的时间戳
            ts = work.top().first;
        }
    }

    return res;
}

int main() {
    vector<int> servers = {3, 3, 2};
    vector<int> tasks = {1, 2, 3, 2, 1, 2};
    vector<int> res = assignTasks(servers, tasks);
    for (auto &x : res) {
        cout << x << " ";
    }
    cout << endl;
}